#include "main/utils.h"
using namespace std;

class Solution {
  public:
    int subarraySum(vector<int>& nums, int k) {
      int ans = 0;
      for (int i = 0; i < nums.size(); ++i) {
        int sum = 0;
        for (int j = i; j >= 0; --j) {
          sum += nums[j];
          if (sum == k) {
            ++ans;
          }
        }
      }
      return ans;
    }

    int subarraySum1(vector<int>& nums, int k) {
      unordered_map<int, int> mp;
      mp[0] = 1;
      int ans = 0, pre = 0;
      for (int i = 0; i < nums.size(); ++i) {
        pre += nums[i];
        if (mp.find(pre - k) != mp.end()) {
          ans += mp[pre - k];
        }
        ++mp[pre];
      }
      return ans;
    }
};

int main() {
  vector<int> input = {1, 1, 1};
  int target = 2;
  Solution su;
  cout << su.subarraySum(input, target) << endl;
  cout << su.subarraySum1(input, target) << endl;
}
